package com.cbd.basic.leetcode.medium;

import com.alibaba.fastjson.JSON;
import lombok.extern.slf4j.Slf4j;

import java.util.*;

/**
 * 电话号码的字母组合
 */
@Slf4j
public class Solution17 {
    public static void main(String[] args) {
        String digits = "238";
        List<String> result = letterCombinations(digits);
        log.info("result = {}", JSON.toJSONString(result));
    }

    public static List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        Deque<String> deque = new ArrayDeque<>();
        for (int i = 0; i < digits.length(); i++) {
            Character digit = digits.charAt(i);
            String letters = map.get(digit);
            if (deque.isEmpty()) {
                for (int j = 0; j < letters.length(); j++) {
                    deque.offer(String.valueOf(letters.charAt(j)));
                }
            } else {
                int size = deque.size();
                for (int j = 0; j < size; j++) {
                    String letter = deque.poll();
                    for (int k = 0; k < letters.length(); k++) {
                        deque.offer(letter + letters.charAt(k));
                    }
                }
            }
        }
        result.addAll(deque);
        return result;
    }
}
